package algorithms;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ParallelMergeSort extends RecursiveTask<int[]> implements SortStrategy {
    private static final int THRESHOLD=31;
    private int[] data;
    private int l;
    private int r;
    private int[] ret;

    public ParallelMergeSort() {
        ;
    }

    public ParallelMergeSort(int[] data, int l, int r) {
        this.data = data;
        this.l = l;
        this.r = r;
    }

    public int[] sort(int[] data) {
        // 排序所调用的方法
        this.data = data.clone();
        this.ret = new int[this.data.length];

        ParallelMergeSort task = new ParallelMergeSort(this.data, 0, this.data.length-1);
        task.fork();
        return task.join();
    }

    public int[] compute() {
        // 线程的计算任务
        if (this.l == this.r) return new int[]{this.data[l]};
        else if ((this.r - this.l) < THRESHOLD) return new SerialMergeSort().sort(Arrays.copyOfRange(this.data, l, r+1));
        else {
            int q = (this.l+this.r)/2;
            // 分配任务给两个子线程
            ParallelMergeSort worker1 = new ParallelMergeSort(this.data, l, q);
            ParallelMergeSort worker2 = new ParallelMergeSort(this.data, q+1, r);
            worker1.fork();
            worker2.fork();
            int[] arr1 = worker1.join();
            int[] arr2 = worker2.join();

            // 归并
            int[] retArr = new int[this.r-this.l+1];
            int index1 = 0, index2 = 0, index=0;
            for (; index1<arr1.length && index2<arr2.length; ){
                if (arr1[index1] <= arr2[index2]) {
                    retArr[index] = arr1[index1];
                    index++;
                    index1++;
                } else {
                    retArr[index] = arr2[index2];
                    index++;
                    index2++;
                }
            }
            if (index1 == arr1.length) {
                for (; index2<arr2.length; index2++, index++) retArr[index] = arr2[index2];
            } else {
                for (; index1<arr1.length; index1++, index++) retArr[index] = arr1[index1];
            }

            return retArr;
        }
    }
}

